package org.leetcode.middle.leetcode654;

import org.leetcode.TreeNode;

import java.util.Arrays;

public class Solution
{


    /**
     *代码随想录
     */
    public TreeNode constructMaximumBinaryTree(int[] nums)
    {
        return constructMaximumBinaryTree(nums,0,nums.length);
    }


    private TreeNode constructMaximumBinaryTree(int []nums,int leftIndex,int rightIndex)
    {
        if (rightIndex-leftIndex==1)
        {
            return new TreeNode(nums[leftIndex]);
        }

        if (rightIndex-leftIndex<1)
        {
            return null;
        }

        int maxIndex = leftIndex;
        int maxValue =nums[maxIndex];

        for (int i = leftIndex+1; i <rightIndex; i++) {
            if (nums[i]>maxValue)
            {
                maxValue=nums[i];
                maxIndex=i;
            }
        }

        TreeNode node = new TreeNode(maxValue);

        node.left=constructMaximumBinaryTree(nums,leftIndex,maxIndex);
        node.right=constructMaximumBinaryTree(nums,maxIndex+1,rightIndex);

        return node;
    }

    /**
     * 成功
     */
    public TreeNode constructMaximumBinaryTree2(int[] nums) {


        if (nums==null|| nums.length==0 )
        {
            return null;
        }

        if (nums.length==1)
        {
            return new TreeNode(nums[0]);
        }

        int maxValue = nums[0];
        int maxValueIndex =0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>maxValue)
            {
                maxValue=nums[i];
                maxValueIndex=i;
            }
        }

        int [] leftNum = new int[maxValueIndex];

        for (int i = 0; i < maxValueIndex; i++) {
            leftNum[i]=nums[i];
        }


        int[]rightNum =new int[nums.length-maxValueIndex-1];

        for (int i = 0; i < rightNum.length; i++) {
            rightNum[i]=nums[maxValueIndex+i+1];
        }


        TreeNode root = new TreeNode(maxValue);

        root.left=constructMaximumBinaryTree2(leftNum);

        root.right=constructMaximumBinaryTree2(rightNum);

        return root;
    }


}
